package megamu.mesh;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;

import quickhull3d.Point3d;
import quickhull3d.QuickHull3D;

import com.jellyfishumbrella.GL.Vertex;
import com.jellyfishumbrella.util.Trace;

public class Voronoi {
	public final double						TOO_CLOSE	= 5;
	public LinkedHashMap<String, Corner>	corners;
	// public float[][] edges;
	LinkedHashMap<Integer, Region>			regions		= new LinkedHashMap<Integer, Region>();
	VoronoiInput<String, Site>				sites;
	protected Delaunay						delaunay;

	LinkedHashMap<String, Edge>				edges		= new LinkedHashMap<String, Edge>();

	public Voronoi() {

		delaunay = new Delaunay();
	}

	public void generate(VoronoiInput<String,Site> baseSites) {
		Trace.getCurrentMethodName();
		sites = baseSites;
		corners = new LinkedHashMap<String, Corner>();
		edges = new LinkedHashMap<String, Edge>();

		if (baseSites == null) {
			// edges = new float[0][4];
			regions = new LinkedHashMap<Integer, Region>();
			return;
		}

		// build points array for qhull
		System.out.println(baseSites.size() + "   " + (baseSites.size() * 3 + 9));
		double qPoints[] = new double[baseSites.size() * 3 + 9];
		System.out.println(qPoints.length);
		//for (int i = 0; i < baseSites.size(); i++) {
		int i1 = 0;
		for(Object currObj: baseSites.values()){
			Site currSite = (Site) currObj;
			qPoints[i1 * 3] = currSite.vert.x();
			qPoints[i1 * 3 + 1] = currSite.vert.z();
			qPoints[i1 * 3 + 2] = -(currSite.vert.x() * currSite.vert.x() + currSite.vert.z() * currSite.vert.z()); // standard half-squared euclidian distance
			i1++;
		}
		// 1
		qPoints[qPoints.length - 9] = -8000D;
		qPoints[qPoints.length - 8] = 0D;
		qPoints[qPoints.length - 7] = -64000000D;
		// 2
		qPoints[qPoints.length - 6] = 8000D;
		qPoints[qPoints.length - 5] = 8000D;
		qPoints[qPoints.length - 4] = -128000000D;
		// 3
		qPoints[qPoints.length - 3] = 8000D;
		qPoints[qPoints.length - 2] = -8000D;
		qPoints[qPoints.length - 1] = -128000000D;

		// prepare quickhull
		Trace.getCurrentMethodName("starting quickHull");
		VoronoiHull quickHull = new VoronoiHull(qPoints);
		Trace.getCurrentMethodName("finishing quickHull");

		Point3d[] vertices = quickHull.getVertices();
		int[][] faces = quickHull.getFaces(QuickHull3D.POINT_RELATIVE + QuickHull3D.CLOCKWISE);
		int[][] faces2 = quickHull.getFaces(QuickHull3D.CLOCKWISE);
		int artifact = 0;

		int[] vertIndices = quickHull.getVertexPointIndices();

		regions = new LinkedHashMap<Integer, Region>();
		int numFaces = faces.length;
		int numFaces2 = faces2.length;
		int numVerts = vertices.length;
		int numSites = baseSites.size();
		int numQPoints = qPoints.length;
		int numVerts2 = vertIndices.length;

		for (int k = 0; k < numFaces; k++) {
			int numFaceVerts = faces[k].length;
			Corner center = new Corner(0, 0, 0);
			for (int i = 0; i < numFaceVerts; i++) {
				int index = faces[k][i];
				Point3d point = vertices[index];
				Vertex currVert = new Vertex(point.x, 0, point.y);
				center.vert.add(currVert);
			}
			center.vert.scale((double) numFaceVerts);
			corners.put(center.toString(), center);
		}

		regions = quickHull.getVoronoi(baseSites);
/*
 * // for (int i = 0; i < numVerts; i++) { for (Object currObj : baseSites) { Site currSite = (Site) currObj; Region newRegion = new Region(); newRegion.site = currSite; newRegion.site.region = newRegion; regions.add(newRegion); }
 * 
 * for (int k = 0; k < numFaces; k++) { Region newRegion = new Region(); int numFaceVerts = faces[k].length; double minDist = 999999; Site center = new Site();
 * 
 * for (int i = 0; i < numFaceVerts; i++) { Point3d A = vertices[faces[k][i]];
 * 
 * Corner newVertA = new Corner(A.x, 0.0, A.y);
 * 
 * for (Region currRegion : regions) { Site currSite = currRegion.site; double dist = newVertA.vert.distance(currSite); if (dist < minDist) { minDist = dist; center = currSite; } } if (minDist == 0.0) { System.out.println("MINDIST: " + minDist); corners.put(newVertA.toString(), newVertA); center.region.addCorner(newVertA); } } } for (int i = 0; i < regions.size(); i++) { Region currRegion = regions.remove(0); ArrayList<Corner> corners2 = new ArrayList<Corner>(currRegion.getCorners()); System.out.println("corners: " + corners2.size()); if (corners2.size() >= 3) { currRegion.pointNormalsUp(); regions.add(currRegion); } }
 */
/*
		int i = 0;
		Trace.log("BASESITES:");
		for (Object currObj : baseSites.values()) {
			Site currSite = (Site) currObj;
			Trace.log(i++ + ": " + currSite.toString());
		}
		
		i = 0;
		Trace.log("\nREGIONS:");
		for (Region currRegion: regions.values()) {
			Site currSite = currRegion.site;
			Trace.log(i++ + "site: " + currSite.toString());
			int j = 0;
			for(Corner currCorner : currRegion.getCorners()){
				Trace.log("  " + j++ + "corner: " + currCorner.toString());
			}
		}

		i = 0;
		Trace.log("\nqPoints:");
		 for (Double qPoint : qPoints) {
		for (int j = 0; j < qPoints.length; j += 3) {
			Trace.log(i++ + ": " + qPoints[j] + ", " + qPoints[j + 1] + ", " + qPoints[j + 2]);
		}

		i = 0;
		Trace.log("\nVertices:");
		for (Point3d vert : vertices) {
			Trace.log(i++ + ": " + vert.toString());
		}

		i = 0;
		Trace.log("\nCorners:");
		Collection<Corner> c = corners.values();
		for (Corner corner : c) {
			Trace.log(i++ + ": " + corner.toString());
		}

		i = 0;
		Trace.log("\nFaceVerts");
		for (int k = 0; k < numFaces; k++) {
			int numFaceVerts = faces[k].length;

			for (int j = 0; j < numFaceVerts; j++) {
				int index = faces[k][j];
				Point3d A = vertices[index];
				Trace.log(i + ": " + " k: " + k + " j: " + j + " index: " + index + "   " + A.toString());
			}
			double x0 = qPoints[faces[k][0] * 3 + 0];
			double y0 = qPoints[faces[k][0] * 3 + 1];
			double x1 = qPoints[faces[k][1] * 3 + 0];
			double y1 = qPoints[faces[k][1] * 3 + 1];
			double x2 = qPoints[faces[k][2] * 3 + 0];
			double y2 = qPoints[faces[k][2] * 3 + 1];

			double v1x = 2 * (x1 - x0);
			double v1y = 2 * (y1 - y0);
			double v1z = x0 * x0 - x1 * x1 + y0 * y0 - y1 * y1;

			double v2x = 2 * (x2 - x0);
			double v2y = 2 * (y2 - y0);
			double v2z = x0 * x0 - x2 * x2 + y0 * y0 - y2 * y2;

			double tmpx = v1y * v2z - v1z * v2y;
			double tmpy = v1z * v2x - v1x * v2z;
			double tmpz = v1x * v2y - v1y * v2x;

			Trace.log(i++ + ": " + new Corner(tmpx / tmpz, 0.0, tmpy / tmpz));
		}
*/
		// }
		// Vertex newVert = new Vertex(faces[i][0], faces[i][1], faces[i][2]);

		// for (int f = 0; f < faceOrder.size(); f++) {
		// int face = faceOrder.get(f);
		// regions[i].addCorner(dualVerts[face]);
		// }
		// }
/*
 * // compute dual points Corner dualVerts[] = new Corner[faces.length];
 * 
 * for (int i = 0; i < faces.length; i++) {
 * 
 * // test if it's the artifact if (faces[i][0] >= baseSites.size() && faces[i][1] >= baseSites.size() && faces[i][2] >= baseSites.size()) artifact = i;
 * 
 * double x0 = qPoints[faces[i][0] * 3 + 0]; double y0 = qPoints[faces[i][0] * 3 + 1]; double x1 = qPoints[faces[i][1] * 3 + 0]; double y1 = qPoints[faces[i][1] * 3 + 1]; double x2 = qPoints[faces[i][2] * 3 + 0]; double y2 = qPoints[faces[i][2] * 3 + 1];
 * 
 * double v1x = 2 * (x1 - x0); double v1y = 2 * (y1 - y0); double v1z = x0 * x0 - x1 * x1 + y0 * y0 - y1 * y1;
 * 
 * double v2x = 2 * (x2 - x0); double v2y = 2 * (y2 - y0); double v2z = x0 * x0 - x2 * x2 + y0 * y0 - y2 * y2;
 * 
 * double tmpx = v1y * v2z - v1z * v2y; double tmpy = v1z * v2x - v1x * v2z; double tmpz = v1x * v2y - v1y * v2x;
 * 
 * dualVerts[i] = new Corner(tmpx / tmpz, 0.0, tmpy / tmpz); if (corners.containsKey(dualVerts[i].toString())) { dualVerts[i] = corners.get(dualVerts[i].toString()); Trace.getCurrentMethodName("mergedVerts: " + corners.size()); } else { corners.put(dualVerts[i].toString(), dualVerts[i]); } }
 * 
 * Trace.getCurrentMethodName("total mergedVerts: " + corners.size() + "   " + dualVerts.length);
 * 
 * // create edge/point/face network // edges = new float[1][4]; int edgeCount = 0; LinkedArray faceNet = new LinkedArray(faces.length); ArrayList<ArrayList<Integer>> pointBuckets = new ArrayList<ArrayList<Integer>>();// IntArray[baseSites.size()]; for (int i = 0; i < baseSites.size(); i++) pointBuckets.add(new ArrayList<Integer>());// new IntArray();
 * 
 * // discover edges Trace.getCurrentMethodName("discover edges"); int newCornerCount = 0; int reuseCornerCount = 0; for (int i = 0; i < faces.length; i++) {
 * 
 * // bin faces to the points they belong with for (int f = 0; f < faces[i].length; f++) { if (faces[i][f] < baseSites.size()) { pointBuckets.get(faces[i][f]).add(i); } }
 * 
 * for (int j = 0; j < i; j++) { if (i != artifact && j != artifact && isEdgeShared(faces[i], faces[j])) {
 * 
 * faceNet.link(i, j);
 * 
 * Corner newCorner1 = new Corner(dualVerts[i].vert.x, 0, dualVerts[i].vert.z); Corner newCorner2 = new Corner(dualVerts[j].vert.x, 0, dualVerts[j].vert.z);
 * 
 * //newCorner1 = corners.get(newCorner1.toString()); //newCorner2 = corners.get(newCorner2.toString());
 * 
 * Edge newEdge = new Edge(); newEdge.corner1 = newCorner1; newEdge.corner2 = newCorner2;
 * 
 * edges.put(newEdge.toString(), newEdge);
 * 
 * newCorner1.neighbors.add(newEdge.corner2); newCorner2.neighbors.add(newEdge.corner1);
 * 
 * edgeCount++;
 * 
 * }
 * 
 * }
 * 
 * }
 * 
 * System.out.println("new: " + newCornerCount + "    reuse: " + reuseCornerCount); Trace.getCurrentMethodName();
 * 
 * // calculate the region for each point regions = new Region[baseSites.size()]; for (int i = 0; i < baseSites.size(); i++) { // IntArray faceOrder = new IntArray(pointBuckets.get(i).size()); ArrayList<Integer> faceOrder = new ArrayList<Integer>();
 * 
 * // add coords of the region in the order they touch, starting with // the convenient first int p = pointBuckets.get(i).get(0);
 * 
 * while (p >= 0) {
 * 
 * faceOrder.add(p);
 * 
 * // find the next coordinate that is in this set that we haven't // used yet int newP = -1; for (int k = 0; k < faceNet.get(p).links.size(); k++) { int neighbor = faceNet.get(p).links.get(k); if (!faceOrder.contains(neighbor) && pointBuckets.get(i).contains(neighbor)) { newP = neighbor; break; } } p = newP;
 * 
 * }
 * 
 * // turn the coordinates into a polygon regions[i] = new Region(pointBuckets.get(i).size()); for (int f = 0; f < faceOrder.size(); f++) { int face = faceOrder.get(f); regions[i].addCorner(dualVerts[face]); }
 * 
 * regions[i].site = (Site) baseSites.get(i); regions[i].site.region = regions[i];
 * 
 * ArrayList<Corner> tempCorners = regions[i].getCorners(); for (int j = 0; j < tempCorners.size(); j++) { Edge tempEdge = new Edge(); tempEdge.corner1 = tempCorners.get(j); if (j < tempCorners.size() - 1) { tempEdge.corner2 = tempCorners.get(j + 1); } else { tempEdge.corner2 = tempCorners.get(0); } Edge tempEdge2 = edges.get(tempEdge.toString()); if (tempEdge2 == null) { edges.put(tempEdge.toString(), tempEdge); tempEdge2 = tempEdge; } if (tempEdge2.site1 == null) { tempEdge2.site1 = regions[i].site; } else if (tempEdge2.site2 == null) { tempEdge2.site2 = regions[i].site; } regions[i].addEdge(tempEdge2); // tempCorners.get(j).isBorder = tempCorners.get(j).isBorder || regions[i].site.isBorder; }
 * 
 * regions[i].pointNormalsUp(); }
 */

	}

	public ArrayList<Region> getRegions() {
		ArrayList<Region> regionList = new ArrayList<Region>();
		for(Region currRegion: regions.values()){
			regionList.add(currRegion);
		}
		return regionList;
	}

	public ArrayList<Edge> getEdges() {
		ArrayList<Edge> edgeList = new ArrayList<Edge>();

		for (Map.Entry<String, Edge> entry : edges.entrySet()) {
			Edge currEdge = (Edge) entry.getValue();
			edgeList.add(currEdge);
		}

		return edgeList;
	}

	public void relax(int steps) {
		Trace.getCurrentMethodName();
		for (int currStep = 0; currStep < steps; currStep++) {
			for (int i = 0; i < regions.size(); i++) {
				Region currRegion = regions.get(i);
				Site currSite = regions.get(i).site;

				//if (!currSite.isBorder) {
					Site averageSite = new Site();
					for (int j = 0; j < currRegion.vertCount(); j++) {
						Vertex currVert = currRegion.getVerts().get(j);
						averageSite.vert.add(currVert);
					}
					averageSite.vert.scale(currRegion.vertCount());

//					sites.set(i, averageSite);
				//}
			}
			generate(sites);
		}
	}

	protected boolean isEdgeShared(int face1[], int face2[]) {
		for (int i = 0; i < face1.length; i++) {
			int cur = face1[i];
			int next = face1[(i + 1) % face1.length];
			for (int j = 0; j < face2.length; j++) {
				int from = face2[j];
				int to = face2[(j + 1) % face2.length];
				if (cur == from && next == to || cur == to && next == from)
					return true;
			}
		}
		return false;
	}

	public void populateRegionNeighbors() {
		for (Map.Entry<String, Edge> entry : edges.entrySet()) {
			Edge currEdge = (Edge) entry.getValue();
			if (currEdge.site1 != null && currEdge.site2 != null) {
				currEdge.site1.region.neighbors.add(currEdge.site2.region);
				currEdge.site2.region.neighbors.add(currEdge.site1.region);
			}
		}
	}
}
